package com.wfm.leetcode.editor.cn;

import java.util.HashMap;

/**
 * 构造两个数据结构：hashmap和双向链表
 * 双向链表实现一写方法，比如addNodeToHead等函数
 * map为了查询时拥有O(1)时间复杂度而创建
 * 新增、删除等操作需要同时操作map和双向链表
 * 时：o(1)
 * 空：o(capacity)
 */
public class POne46LRU缓存{
//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {
    DlinkedNode head;
    DlinkedNode tail;
    HashMap<Integer,DlinkedNode> map;
    private int capacity;

    class DlinkedNode{
        int key;
        int value;
        DlinkedNode pre;
        DlinkedNode next;

        public DlinkedNode(){}
        public DlinkedNode(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DlinkedNode();
        tail = new DlinkedNode();
        head.next = tail;
        tail.pre=head;
        map = new HashMap<Integer,DlinkedNode>();
    }
    
    public int get(int key) {
        DlinkedNode orDefault = map.get(key);
        if(orDefault==null){
            return -1;
        }
        moveNodeToHead(orDefault);
        return orDefault.value;
    }
    
    public void put(int key, int value) {
        if(!map.containsKey(key)){
            DlinkedNode newNode = new DlinkedNode(key, value);
            addNodeToHead(newNode);
            map.put(key,newNode);
            if(map.size()>this.capacity){
                DlinkedNode dlinkedNode = delNode(tail.pre);
                map.remove(dlinkedNode.key);
            }
        }else {
            DlinkedNode o = map.get(key);
            o.value = value;
            map.put(key,o);
            moveNodeToHead(o);
        }
    }
    void addNodeToHead(DlinkedNode node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }

    void moveNodeToHead(DlinkedNode node){
        DlinkedNode del = delNode(node);
        addNodeToHead(del);
    }

    DlinkedNode delNode(DlinkedNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
        return node;
    }
}

//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
    }
}